package Algorithm.Sort;

import java.util.Arrays;

/**
 * 选择排序：
 * 每一次从无序区间选出最大（或最小）的一个元素，
 * 存放在无序区间的最后（或最前），
 * 直到全部待排序的数据元素排完 。
 * 每轮都找到一组数据中最小的数依次放在数组前面。
 * 与冒泡排序的不同：冒泡排序在找数的时候，
 * 每次比较都需要进行数据交换，而选择排序是两两对比 记录数据的索引，找到数据后只进行一次交换。
 */
public class SelectionSort {

    public static void main(String[] args) {
        int[] arr = {2,1,5,3,7,8,4,9};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    // 选择排序
    // 每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），
    // 直到全部待排序的数据元素排完。
    public static void selectionSort(int[] arr){
        // 最开始，无序区间[0...n]  有序区间[]
        // 当无序区间只剩下一个元素时，整个集合已经有序
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]){
                    min = j;
                }
            }
            if(i != min){
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    }

}
